package chapter01;

public class IsMatch44 {
    /**
     * dp问题
     * dp[i][j] 表示s的前i个字符与p的前j个字符的匹配结果
     * 很容易能想到先对第一行与第一列进行初始化
     * 第一行:s为""的时候与p匹配情况
     *       dp[0][0]=true
     *       当p[j-1]=='*'  p[j-1]可以匹配s中任意多字符 由于s已经是空字符串 那么[0][j]应和前一位相同 dp[0][j]==dp[0][j-1]
     * 第一列:p为""时与s匹配情况
     *       都不匹配 dp[i][0]==false 创建布尔型数组对象有缺省值false 可以省略
     * 其他情况
     *      1) s[i-1]==p[j-1]||p[j-1]=='?' s第i个字符与p第j个字符必须要进行匹配 匹配结果与s前i-1个字符匹配p前j-1个字符相同
     *         dp[i][j]==dp[i-1][j-1]
     *      2) p[j-1]=='*' p的第j个字符可以任意匹配s中字符
     *         a.匹配s中0个字符
     *           dp[i][j]==dp[i][j-1]
     *         b.匹配s中k个字符
     *           先匹配s中一个字符s[i-1] 但j不变 让'*'继续与s匹配k-1个字符
     *           dp[i][j]==dp[i-1][j]
     *         c.综合情况a、b
     *           dp[i][j]==dp[i-1][j] || dp[i][j-1]
     *      3) s[i-1]!=p[j-1] && s[i-1]与p[j-1]为'a'~'z'间任意字符
     *          dp[i][j]=false
     *          创建布尔型数组对象有缺省值false 可以省略
     * */
    public boolean isMatch(String s, String p) {
        if(s.length()<1&&p.length()<1){
            return true;
        }
        int sLength=s.length();
        int pLength=p.length();
        boolean[][] dp=new boolean[sLength+1][pLength+1];
        dp[0][0]=true;
        for(int j=1;j<=pLength;j++){
            if(p.charAt(j-1)=='*'){
                dp[0][j]=dp[0][j-1];
            }
        }
        for(int i=1;i<=sLength;i++){
            for(int j=1;j<=pLength;j++){
                if(s.charAt(i-1)==p.charAt(j-1)||p.charAt(j-1)=='?'){
                    dp[i][j]=dp[i-1][j-1];
                }else if(p.charAt(j-1)=='*'){
                    dp[i][j]=dp[i][j-1]||dp[i-1][j];
                }
            }
        }
        return dp[sLength][pLength];
    }

}
